iT邦幫忙

2021 iThome 鐵人賽

DAY 15
0
自我挑戰組

每日LeetCode解題紀錄系列 第 15

LeetCode解題 Day15

  • 分享至 

  • xImage
  •  

978. Longest Turbulent Subarray

https://leetcode.com/problems/longest-turbulent-subarray/


題目解釋

請從陣列arr 找出 "turbulent" 子陣列,turbulent意思如下:

arr[i] 大於arr[i+1]時,arr[i+2] 也要大於arr[i+1],簡單來說就是上個數字比較大(小),下個數字也要較大(小)

example

https://i.imgur.com/QdfqdVN.png


解法

今天有點來不及了,所以先拿別人的程式碼講解

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        
        def cmp(a, b):
            if a > b: return 1
            elif a < b: return -1
            else: return 0
        
        N = len(arr)
        ans = 1
        anchor = 0

        for i in range(1, N):
            c = cmp(arr[i-1], arr[i])
            if c == 0:
                anchor = i
            elif i == N-1 or c * cmp(arr[i], arr[i+1]) != -1:
                ans = max(ans, i - anchor + 1)
                anchor = i
        return ans

陣列中比大小會出現 >、<、= 三種狀況,我們將他對應到 1、-1、0

接著我們比較前一項(arr[i-1], arr[i]),如果等於0就記錄位置當作起點

接著比較後項的對應數字,並乘上前項對應數字:

  • 如果等於-1就代表數字間的大小於有變換,也就是我們要記錄的Turbulent
  • 如果不等於-1就代表數字連續出現大於或小於,那就記錄位置當作起點

解法2

  • 9/16補上自己的想法

兩個數字之間的關係就只有三種,所以我們只要記錄前一組碰到的關係就好

  • 當前一組是等於,我們就記錄長度1
  • 當前一組是大於或小於,我們就記錄起始的長度2,或是長度繼續加一
class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        ans = 1
        sign = '>'
        
        count = 1
        for i in range(1, len(arr)):
                
            if arr[i-1] == arr[i]:
                count = 1
            
            if arr[i-1] > arr[i]:
                if sign == '>': count = 2
                else: count += 1
                    
                sign = '>'
                    
            if arr[i-1] < arr[i]:
                if sign == '<': count = 2
                else: count += 1
                    
                sign = '<'
                
            ans = max(ans, count)
        
        return ans
        

閒聊

時間趕上 SAFE


上一篇
LeetCode解題 Day14
下一篇
LeetCode解題 Day16
系列文
每日LeetCode解題紀錄30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言